package dp;

import java.util.Arrays;

/**
 * @author pengfei.hpf
 * @date 2020/3/12
 * @verdion 1.0.0
 * 935. 骑士拨号器
 * 国际象棋中的骑士可以按下图所示进行移动：
 *
 *  .
 *
 *
 * 这一次，我们将 “骑士” 放在电话拨号盘的任意数字键（如上图所示）上，接下来，骑士将会跳 N-1 步。每一步必须是从一个数字键跳到另一个数字键。
 *
 * 每当它落在一个键上（包括骑士的初始位置），都会拨出键所对应的数字，总共按下 N 位数字。
 *
 * 你能用这种方式拨出多少个不同的号码？
 *
 * 因为答案可能很大，所以输出答案模 10^9 + 7。
 *
 *
 *
 * 示例 1：
 *
 * 输入：1
 * 输出：10
 * 示例 2：
 *
 * 输入：2
 * 输出：20
 * 示例 3：
 *
 * 输入：3
 * 输出：46
 *
 *
 * 提示：
 *
 * 1 <= N <= 5000
 */
public class KnightDialer {
    int[][] moves = new int[][]{
            {4,6},{6,8},{7,9},{4,8},{3,9,0},
            {},{1,7,0},{2,6},{1,3},{2,4}};

    public int knightDialer(int N) {
        if(N <= 0){
            return 0;
        }
        long[][] dp = new long[2][10];
        Arrays.fill(dp[0], 1L);
        long sum = 0;
        int row = 0;

        long M = (long)(Math.pow(10,9) + 7);
        for(int i = 2; i <= N; i ++){
            int curRow = (row + 1) % 2;
            for(int n = 0; n <= 9; n ++){
                dp[curRow][n] = getSum(dp, n, row, M);
            }
            row = curRow;
        }
        for(int i = 0; i < 10; i ++){
            sum += dp[row][i] % M;
        }
        return (int)(sum % M);

    }

    private long getSum(long[][] dp, int num, int row, long M){
        long sum = 0;
        int[] jumpTo = moves[num];
        for(int i: jumpTo){
            sum += dp[row][i]% M;
        }
        return sum;
    }
}
